package com.zhangxiaofanfan.hotcode.fourth.third;

/**
 * <a href="https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked">接雨水</a>
 *
 * @author zhangxiaofanfan
 * @date 2024-05-22 22:29:15
 */
public class HotCode007 {
    public static void main(String[] args) {

    }

    public int trap(int[] height) {
        if (height == null || height.length < 2) {
            return 0;
        }
        int[][] dp = new int[height.length][2];
        for (int i = 1; i < height.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], height[i - 1]);
        }
        for (int i = height.length - 2; i >= 0; i--) {
            dp[i][1] = Math.max(dp[i + 1][1], height[i + 1]);
        }
        int count = 0;
        for (int i = 1; i < height.length - 1; i++) {
            count += Math.max((Math.min(dp[i][0], dp[i][1]) - height[i]), 0);
        }
        return count;
    }
}
